package com.leetcode.shuzu;

public class RotateTest {
    public static void main(String[] args) {
//        int[] nums = {1,2,3,4,5,6,7};
//        int k = 3;
//        int[] newArr = rotate(nums, k);
//        for (int i = 0; i < newArr.length; i++) {
//            sop(newArr[i]+", ");
//        }

//        int[] nums = {-1,-100,3,99};
//        int k = 2;
        int[] nums = {1,2};
        int k = 2;
        int[] newArr2 = rotate2(nums, k);
        for (int i = 0; i < newArr2.length; i++) {
            sop(newArr2[i]+", ");
        }
    }

    /**
     * 方法一中使用额外数组的原因在于如果我们直接将每个数字放至它最后的位置，
     * 这样被放置位置的元素会被覆盖从而丢失。
     * 因此，从另一个角度，我们可以将被替换的元素保存在变量 temp 中，从而避免了额外数组的开销。
     *
     * 我们从位置 0开始，最初令 temp=nums[0]。根据规则，位置 0 的元素会放至 (0+k)mod n 的位置，
     * 令 x=(0+k) mod n，此时交换 temp 和 nums[x]，完成位置 x 的更新。
     * 然后，我们考察位置 x，并交换 temp 和 nums[(x+k)modn]，
     * 从而完成下一个位置的更新。不断进行上述过程，直至回到初始位置 0。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode-solution-nipk/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param nums
     * @param k
     * @return
     */
    private static int[] rotate2(int[] nums, int k) {
        int count = 0;
        int x = 0;
        int i = 0;
        int temp = nums[i];

        while(true){
            x = (x+k) % nums.length;

            nums[x] = nums[x] ^ temp;
            temp = nums[x] ^ temp;
            nums[x] = nums[x] ^ temp;
            count++;

            if(x == i){
                i++;
                if (i == (nums.length/2 +1)){
                    break;
                }
                temp = nums[i];
                x=i;
            }
            if(count == nums.length){
                break;
            }
        }
        return  nums;
    }

    private static void sop(Object obj) {
        System.out.print(obj);
    }

    /**
     * 方法一：使用额外的数组
     * 我们可以使用额外的数组来将每个元素放至正确的位置。
     * 用 nn表示数组的长度，我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+k)\bmod n(i+k)modn 的位置，
     * 最后将新数组拷贝至原数组即可。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode-solution-nipk/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param nums
     * @param k
     * @return
     */
    private static int[] rotate(int[] nums, int k) {
        int[] newArr = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            newArr[(i+k)  % nums.length] = nums[i];
        }
        return  newArr;
    }
    
    
}
